package offer;

/**
 * @Author Elephas
 * @Date 2022/1/30
 **/
public interface CanFinish {
    boolean canFinish(int numCourses,int[][] prerequisites);
}
class CanFinishImpl1 implements CanFinish{

    @Override
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] set = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            set[i] = -1;
        }
        for(int[] prerequisite : prerequisites){
            int cur = prerequisite[0];
            int pre = prerequisite[1];
            if(cur == -1) {
                set[cur] = pre;
            }else{
                int slow = cur,fast = cur;
                while(slow != -1 && fast != -1){
                    slow = set[slow];
                    fast = set[fast];
                    if(fast != -1){
                        fast = set[fast];
                    }
                    if(slow == fast){
                        // has cycle
                        return false;
                    }
                }
                // no cycle
                set[cur] = pre;
            }
        }
        return hasCycle(set);
    }
    private boolean hasCycle(int[] set){
        int slow,fast;
        for (int i = 0; i < set.length; i++) {
            slow = fast = i;
            while(slow != -1 || fast != -1){
                slow = set[slow];
                set[fast] = set[fast];
                if(fast != -1){
                    set[fast] = set[fast];
                    if(fast == slow){
                        return false;
                    }
                }
            }
        }
        return true;
    }
}
class CanFinishImpl2 implements CanFinish{

    @Override
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        boolean[][] hasPath = new boolean[numCourses][numCourses];
        for (int i = 0; i < numCourses; i++) {
            for (int j = 0; j < numCourses; j++) {
                hasPath[i][j] = false;
            }
        }
        for(int[] prerequisite : prerequisites){
            int cur = prerequisite[0];
            int pre = prerequisite[1];
            hasPath[cur][pre] = true;
        }
        return hasCycle(numCourses, hasPath);
    }
    private boolean hasCycle(int n,boolean[][] graph){
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(graph[i][j]){
                    int slow = j;
                    int fast = j;

                }
            }
        }
        return true;
    }
}
